#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
class Solution
{
public:
    int repeatedNTimes(vector<int> &nums)
    {
        unordered_map<int, int> numsMap;
        for (auto &num : nums)
        {
            numsMap[num]++;
        }
        for (auto &[k, v] : numsMap)
        {
            if (v == nums.size() / 2)
            {
                return k;
            }
        }
        return -1;
    }
    int repeatedNTimes_1(vector<int> &nums)
    {
        unordered_set<int> found;
        for (int num : nums)
        {
            if (found.count(num))
            {
                return num;
            }
            found.insert(num);
        }
        // 不可能的情况
        return -1;
    }
    int repeatedNTimes_2(vector<int> &nums)
    {
        int n = nums.size() / 2;
        int cnt[10010];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < 2 * n; i++)
        {
            cnt[nums[i]]++;
        }
        for (int i = 0; i < 10010; i++)
        {
            if (cnt[i] == n)
                return i;
        }
        return -1;
    }

    /**
     * @brief 数学判断出现的位置
     *  n+2(n−1)=3n−2
     * @param nums
     * @return int
     */
    int repeatedNTimes_3(vector<int> &nums)
    {
        int n = nums.size();
        for (int gap = 1; gap <= 3; ++gap)
        {
            for (int i = 0; i + gap < n; ++i)
            {
                if (nums[i] == nums[i + gap])
                {
                    return nums[i];
                }
            }
        }
        // 不可能的情况
        return -1;
    }
    /**
     * @brief 随机选择 期望O(1)
     *
     * @param nums
     * @return int
     */
    int repeatedNTimes(vector<int> &nums)
    {
        int n = nums.size();
        mt19937 gen{random_device{}()};
        uniform_int_distribution<int> dis(0, n - 1);

        while (true)
        {
            int x = dis(gen), y = dis(gen);
            if (x != y && nums[x] == nums[y])
            {
                return nums[x];
            }
        }
    }
};
int main()
{
    Solution s;
    vector<int> nums = {2, 6, 2, 1};
    cout << s.repeatedNTimes(nums) << endl;
    return 0;
}